package leetcode;

/**
 * 超级丑数
 编写一段程序来寻找第 n 个超级丑数。

 超级丑数是指其所有质因数都在长度为k的质数列表primes中的正整数。例如，[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]，是给定长度为 4 的质数列表primes = [2, 7, 13, 19]的前 12 个超级丑数。

 注意:
 (1) 1是任何给定的primes的超级丑数。
 (2) 给定primes中的数字以升序排列。
 (3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
 (4) 第n个超级丑数可以认为在32位有符整数的表示范围内。


 */
public class Code313 {
    public static void main(String[] args) {
        System.out.println(new Code313().nthSuperUglyNumber(6,new int[]{2}));

    }
    public int nthSuperUglyNumber(int n, int[] primes) {
        // write your code here
        int[] ugarr = new int[n];
        ugarr[0] = 1;
        int[] item = new int[primes.length];//分别对应的2,3,5 的被乘数的下标
//        int[] itemx= new int[3];//分别对应2,3,5 的乘数
//        itemx[0]=2;
//        itemx[1]=3;
//        itemx[2]=5;
        for (int a = 1; a < ugarr.length; a++) {
            int index=0;
            for (int b = 0; b < primes.length; b++) {
                if (ugarr[item[b]]*primes[b]<ugarr[item[index]]*primes[index]){
                    index=b;
                }
            }
            for (int b = 0; b <  primes.length; b++) {
                if (b!=index&&ugarr[item[b]]*primes[b]==ugarr[item[index]]*primes[index]){
                    item[b]++;
                }
            }
            ugarr[a]=ugarr[item[index]]*primes[index];
            item[index]++;
        }
        return ugarr[n - 1];
    }
}
